/*
	字符串匹配
	匹配T是否是S的一串
*/

#include<stdio.h>
#include<string.h>

int stringMatching(char *S, char *T)
{
	int s = 0,t = 0,lens,lent;
	lens = strlen(S);
	lent = strlen(T);

	for (s = 0; s <= lens - lent; s++)
	{
		for (t = 0;t < lent; t++)
		{
			if (T[t] != S[s+t])
				break;

			if (t == lent - 1)
				return 1;
		}


	}
}


/*
	kmp
*/
void Pi(char *P, int *PI)
{//获取PI数组
	int i = 1, j = 0; m;
	m = strlen(P);

	PI[0] = 0;

	for (i = 1; i < m; i++)
	{
		if (P[i] == P[j])
		{
			j++;
			PI[i] = j;
		}

		while ( (j > 0) && P[i] != P[j])
		{
			j = PI[j-1];
		}
	}
}

void KmpMatching(char *T,char *P)
{
	int n,m,q,i;

	n = strlen(T);
	m = strlen(P);

	int PI[m] = {0};
	Pi(P, PI);//构造PI函数

	q = 0;

	for (i = 0; i < n; i++)
	{
		if (P[q] == T[i])
			q++;

		while ( (q > 0) && P[i] != P[q])
		{
			q = PI[q - 1];
		}

		if (q == m)
		{
			printf("%d\n",i - m + 1);
			p = PI[q - 1];//继续匹配
		}
	}
}